/**
*   @file hash.c
*   Implementacion de un ADT para manejo de tablas de hash.
*   Fecha de ultima modificacion 06/11/2007.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../hashADT/hash.h"

/**
*   \var LIMITSIZE
*	Constante con el porcentaje del tamanio maximo de la tabla de hash.
*/
#define LIMITSIZE	0.75


/**
*	\struct compositeT
* 	Estructura del elemento dentro de la tabla de hash ordenada.
* 	@param hashT Elemento que se inserta en la tabla de hash.
* 	@param cant Cantidad de hashT dentro de la tabla.
*/ 
typedef struct {
	hashT		value;
	int			cant;
} compositeT;

/**
*	\struct tableElement
* 	Estructura del elemento dentro del  vector de la tabla de hash.
* 	@param hashT Elemento que se hashea y se contabiliza.
* 	@param cant Cantidad de hashT dentro de la tabla.
* 	@param status Estado de la celda en el vector de la tabla de hash segun eraseT.
*/ 
typedef struct {
	hashT		value;
	int 		cant;
	eraseT		status;
}tableElement;

/**
*	\struct hashCDT
* 	Header de la tabla de hash.
* 	@param table Vector de tableElement.
* 	@param hashfunction Puntero a la funcion de hasheo.
* 	@param cmpElement Puntero a la funcion de comparacion.
* 	@param dim Dimension de la tabla de hash.
*/ 
struct hashCDT
{
	tableElement *	 	table;
	fnHash				hashfunction;
	fnCmp				cmpElement;
	int 				dim;
};

static int  Precondition(void * condicion);
static int reHash(hashADT hashtable, int olddim, tableElement * newtable);
static compositeT * createTable(hashADT hashtable, int * dim);
static int cmpQuantity(const void * quantityA, const void * quantityB);


hashADT
newHash(fnCmp cmpElement, fnHash hashfunction)
{
	hashADT hashtable;
	int i;
	
	if (!Precondition(hashfunction) || !Precondition(cmpElement))
		return NULL;
		
	if ( (hashtable = malloc(sizeof(struct hashCDT))) == NULL )
		return NULL;
		
	/* 	Inicializa el header quadTree y el header */
		
	if ( (hashtable -> table = malloc(sizeof(tableElement) * SLOTS)) == NULL)
	{
		free(hashtable);
		return NULL;
	}
	
	hashtable -> hashfunction = hashfunction;
	hashtable -> cmpElement = cmpElement;
	hashtable -> dim = SLOTS;
	
	/* inicializa a todo el arreglo con bajas fisicas */
	
	for (i = 0 ; i < SLOTS ; i++)
	{
		hashtable -> table[i].value = NULL;
		hashtable -> table[i].status = BAJA_FISICA;
	}
	
	return hashtable;
	
}

int
insertKey(hashADT hashtable, hashT element, int reps)
{
	int key, olddim;
	int i = 0, logictimes = 0;
	tableElement auxi, * auxi2;
	
	if (!Precondition(hashtable) || !Precondition(element) || reps <= 0)
		return 0;
	
	key = hashtable -> hashfunction(element, hashtable -> dim);
	
	if (key == -1)
		return 0;
	
	/* mientras cantidad de inserciones sea menor que los slots, y (en table[i]
	 * haya baja logica o (table[i] esta ya ocupada y elemento en table[i] != element)
	 */
	
	while (i != hashtable -> dim && ((hashtable -> table[key].status ==  BAJA_LOGICA) || (hashtable -> table[key].status == OCCUPIED &&  (hashtable -> cmpElement(hashtable -> table[key].value, element) == 0))))
	{
		i++;
		key = (key + 1) % hashtable -> dim;
		
	/* Si la posicion en la tabla de hash es la primera baja logica que se encuentra,
	 * se la almacena en una variable auxiliar para posterior uso
	 */ 	
		
		if (hashtable -> table[key].status == BAJA_LOGICA && logictimes == 0)
		{
			auxi = hashtable -> table[key];
			logictimes = 1;
		}  
	}
	
	if ( (hashtable -> cmpElement(hashtable -> table[key].value, element)) == 1)
	{
			hashtable -> table[key].cant += reps;
			return 1;
	}
	
	/* si la tabla esta 75% llena, entonces se agranda */
	
	
	else if (i >= (int)((double)hashtable -> dim * LIMITSIZE))
	{
		if ( (auxi2 = calloc(hashtable -> dim * 2, sizeof(tableElement)))== NULL)
		{
			freeHash(hashtable);
			return 0;
		}
		
		olddim = hashtable -> dim;
		
		
		/* actualizo dim de la tabla */
		
		hashtable -> dim *= 2;
				
		if (reHash(hashtable, olddim, auxi2) == 0)
			return 0;
		
		insertKey(hashtable, element, reps);
	}
	else
	{
		if (logictimes == 1)
		{
			/* inserta en la primera baja logica encontrada */
			auxi.value = element;
			auxi.status = OCCUPIED;
			auxi.cant = reps;
		}
		else
		{
			/* inserta en la baja fisica que se encontro */
			hashtable -> table[key].value = element;
			hashtable -> table[key].status = OCCUPIED;
			hashtable -> table[key].cant = reps;
		}
	}
	
	return 1;
	
}

void *
quantitySort(hashADT hashtable, int * dim)
{
	compositeT * table;
	int dim2;
	
	if(!Precondition(hashtable) || !Precondition(dim))
		return NULL;
	
	table = createTable(hashtable, &dim2);
	qsort(table, dim2, sizeof(compositeT), cmpQuantity);
	*dim = dim2;
	return table;
}

void
printSorted(const void * sortedTable, int dim, fnPrint printfunction, int totalamount)
{
	int i;
	double proportion;
	const compositeT * auxi;
	
	auxi = sortedTable;
	
	if (!Precondition((void *)auxi) || !Precondition(printfunction) || totalamount <= 0)
		return;
	
	for (i = 0 ; i < dim ; i++)
	{
		printfunction(auxi[i].value);
		printf("%2d ", auxi[i].cant);
		proportion = (double)auxi[i].cant / totalamount * 100.0;
		printf("- %3.5g%% \n", proportion);
	}
	
	return;
}


int lookUp(hashADT hashtable, hashT element)
{
	int key = hashtable -> hashfunction(element, hashtable -> dim);
	int i = 0;
	
	if (!Precondition(element) || !Precondition(hashtable))
		return 0;
	
	while(i != hashtable -> dim && ((hashtable -> table[i].status ==  BAJA_LOGICA) ||
		 (hashtable -> table[key].status == OCCUPIED && 
		  hashtable -> cmpElement(hashtable -> table[i].value, element) == 0)))
	{
		i++;
		key = (key + 1) % hashtable -> dim;
	}
	
	if (hashtable -> table[key].value != NULL)
		if (hashtable -> cmpElement(hashtable -> table[key].value, element) == 1)
			return 1;
	
	return 0;
}

void 
freeHash(hashADT hashtable)
{		
	free(hashtable -> table);
	free(hashtable);
	
	return;
}

static int
Precondition(void * condicion)
{
	if (condicion == NULL)
		return 0;
		
	return 1;
}

static int
reHash(hashADT hashtable, int olddim, tableElement * newtable)
{
	int i, newkey;
	tableElement * auxi;
	
	auxi = hashtable -> table;
	hashtable -> table = newtable;
	
	for (i = 0 ; i < olddim ; i++)
	{
		newkey = hashtable -> hashfunction(auxi[i].value, hashtable -> dim);
		if (newkey != -1)
				insertKey(hashtable, auxi[i].value, auxi[i].cant);
			
	}
	return 1;
}

static compositeT *
createTable(hashADT hashtable, int * dim)
{
	compositeT * colours = NULL;
	compositeT * auxi;
	int i, cantColors = 0;
	
	
	
	for (i = 0 ; i < hashtable -> dim ; i++)
	{
		if (hashtable -> table[i].status == OCCUPIED)
		{
			if (cantColors % SLOTS == 0)
			{
				if ( (auxi = realloc(colours, (cantColors + SLOTS) * sizeof(compositeT))) == NULL)
				{
					free(colours);
					return NULL;
				}
				
				colours = auxi;
			}
			
			colours[cantColors].value = hashtable -> table[i].value;
			colours[cantColors].cant = hashtable -> table[i].cant;
			cantColors++;
		}
	}
	
	*dim = cantColors;
	return colours;
}

static int
cmpQuantity(const void * quantityA, const void * quantityB)
{
	const compositeT * auxi1, *auxi2;
	
	auxi1 = quantityA;
	auxi2 = quantityB;
	
	if (auxi1 -> cant < auxi2 -> cant)
		return 1;
	else if(auxi1 -> cant > auxi2 -> cant)
		return -1;
	
	return 0;
}
